package net.xuele.learn.dancing.tree;

import net.xuele.learn.dancing.TreeNode;

/**
 * leetcode 110
 * 树是否是高度平衡的
 *
 * 核心思想是递归，左右子树是否是平衡的
 * 高度不平衡的三种情况：
 *      1、左子树不平衡
 *      2、右子树不平衡
 *      3、左右子树的高度之差的绝对值大于1
 */
public class IsBalanced {

    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }

    private int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 左子树的高度
        int lh = height(root.left);
        // 右子树的高度
        int rh = height(root.right);
        if (lh >= 0 && rh >= 0 && Math.abs(lh - rh) <= 1) {
            return Math.max(lh, rh) + 1;
        } else {
            return -1;
        }
    }

    public static void main(String[] args) {

    }
}
